/// 元素相等性判断函数类型
///
/// # 参数
/// - `value1`: 第一个值的不可变引用
/// - `value2`: 第二个值的不可变引用
///
/// # 返回值
/// 返回 `true` 表示相等，`false` 表示不相等
pub type SortedArrayEqualFunc<T> = fn(value1: &T, value2: &T) -> bool;

/// 元素比较函数类型
///
/// # 参数
/// - `value1`: 第一个值的不可变引用
/// - `value2`: 第二个值的不可变引用
///
/// # 返回值
/// 返回 [`std::cmp::Ordering`] 表示排序关系
pub type SortedArrayCompareFunc<T> = fn(value1: &T, value2: &T) -> std::cmp::Ordering;

/// 自动排序且可动态调整大小的泛型数组结构
///
/// 使用 Vec<T> 进行元素存储，通过比较函数维护排序状态
/// 通过函数指针实现自定义比较和相等性判断逻辑
#[derive(Debug)]
pub struct SortedArray<T> {
    /// 底层存储容器，元素始终按 cmp_func 定义的顺序排列
    data: Vec<T>,

    /// 元素相等性判断函数（来自 SortedArrayEqualFunc 类型别名）
    equ_func: SortedArrayEqualFunc<T>,

    /// 元素比较排序函数（来自 SortedArrayCompareFunc 类型别名）
    cmp_func: SortedArrayCompareFunc<T>,
}


impl<T> SortedArray<T> {
    /// 获取数组中元素的数量
    ///
    /// # 返回
    /// 当前存储的元素个数
    pub fn len(&self) -> usize {
        self.data.len()
    }

    /// 获取指定索引处元素的不可变引用
    ///
    /// # 参数
    /// - `index`: 元素索引位置
    ///
    /// # 返回
    /// 返回 `Some(&T)` 当索引有效，否则返回 `None`
    pub fn get(&self, index: usize) -> Option<&T> {
        self.data.get(index)
    }
}

impl<T> SortedArray<T> {
    /// 创建新的自动排序数组实例
    ///
    /// # 参数
    /// - `capacity`: 初始容量（0时使用默认16）
    /// - `equ_func`: 元素相等性判断函数
    /// - `cmp_func`: 元素比较排序函数
    pub fn new(
        mut capacity: usize,
        equ_func: SortedArrayEqualFunc<T>,
        cmp_func: SortedArrayCompareFunc<T>,
    ) -> Self {
        if capacity == 0 {
            capacity = 16;
        }

        Self {
            data: Vec::with_capacity(capacity),
            equ_func,
            cmp_func,
        }
    }
}

impl<T> SortedArray<T> {
    /// 二分查找首个匹配元素的左边界
    fn first_index(&self, data: &T, mut left: usize, mut right: usize) -> usize {
        while left < right {
            let mid = left + (right - left) / 2;
            match (self.cmp_func)(data, &self.data[mid]) {
                std::cmp::Ordering::Greater => left = mid + 1,
                _ => right = mid,
            }
        }
        left
    }

    /// 二分查找最后一个匹配元素的右边界
    fn last_index(&self, data: &T, mut left: usize, mut right: usize) -> usize {
        while left < right {
            let mid = left + (right - left) / 2;
            match (self.cmp_func)(data, &self.data[mid]) {
                std::cmp::Ordering::Less => right = mid,
                _ => left = mid + 1,
            }
        }
        right
    }

    /// 查找元素在数组中的索引
    pub fn index_of(&self, data: &T) -> Option<usize> {
        let mut left = 0;
        let mut right = self.data.len();

        while left < right {
            let mid = left + (right - left) / 2;
            match (self.cmp_func)(data, &self.data[mid]) {
                std::cmp::Ordering::Less => right = mid,
                std::cmp::Ordering::Greater => left = mid + 1,
                std::cmp::Ordering::Equal => {
                    let first = self.first_index(data, left, mid);
                    let last = self.last_index(data, mid + 1, right);
                    return (first..last)
                        .find(|&i| (self.equ_func)(data, &self.data[i]));
                }
            }
        }
        None
    }
}

impl<T> SortedArray<T> {
    /// 清空数组中的所有元素，保留当前容量
    ///
    /// 该方法将内部存储容器的长度设置为0，但保留已分配的容量
    pub fn clear(&mut self) {
        self.data.clear();
    }
}

impl<T> SortedArray<T> {
    /// 向有序数组中插入新元素，保持数组有序性
    ///
    /// # 参数
    /// - `value`: 要插入的泛型元素
    ///
    /// # 返回值
    /// 始终返回插入位置索引，利用 Vec 的自动内存管理确保操作成功
    /// 向有序数组中插入新元素，保持数组有序性
    ///
    /// # 参数
    /// - `value`: 要插入的泛型元素
    ///
    /// # 返回值
    /// 始终返回插入位置索引，利用 Vec 的自动内存管理确保操作成功
    pub fn insert(&mut self, value: T) -> usize {
        let index = self.data
            .binary_search_by(|x| (self.cmp_func)(x, &value))
            .unwrap_or_else(|i| i);
        self.data.insert(index, value);
        index
    }

    /// 移除指定索引范围内的元素
    ///
    /// # 参数
    /// - `index`: 起始索引位置（包含）
    /// - `length`: 需要移除的连续元素数量
    ///
    /// # 注意
    /// 当索引范围无效时静默返回，不会触发 panic
    pub fn remove_range(&mut self, index: usize, length: usize) {
        if index >= self.data.len() || index + length > self.data.len() {
            return;
        }
        self.data.drain(index..index+length);
    }

    /// 移除指定索引处的单个元素
    ///
    /// # 参数
    /// - `index`: 需要移除的元素索引位置
    pub fn remove(&mut self, index: usize) {
        self.remove_range(index, 1);
    }
}